package alg.array;

import java.util.Arrays;

/**
 * @author:yuziji
 * @create: 2023-05-05 15:44
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
 * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 */
public class ErFenChaZhao {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println(search(arr, 5));
    }


    /**
     * 利用二分查找法解决此问题
     *
     * 定义两个下标left,right
     * left用来表示数组第一个元素,right用来表示数组最后一个元素
     * 循环条件left<=right
     * 1)
     * 取left和right的中间下标mid,即mid=(left+right)/2;
     * 判断nums[mid]是否和target相等
     * 如果相等，则mid就是需要返回的下标
     * 如果target>mid,则说明target在mid-right之间(暂不考虑target不在数组的情况)
     *          则让下标left指向mid+1的位置,即left=mid+1。然后循环执行1)之后的步骤
     * 如果target<mid,则说明target在left-mid之间(同样不考虑target不在数组中的情况)
     *          则让下标right指向mid-1的位置,即right=mid-1，然后循环执行1)之后的步骤
     * 循环结束时,target不满足以上三个条件时，说明target不在数组中，则直接返回-1
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if (nums[mid]==target){
                return mid;
            }else if (target>nums[mid]){
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return -1;
    }
}
